package nowCoder;

public class FormALineCoinProblem {//didn't solve.I should use DP.
	public int getWinValue(int[] arr) {
		if(arr==null || arr.length==0)
			return 0;
		int rst1=0,rst2=0;
		int start=0,end=arr.length-1;
		int count= 0;
		while(start<end){
			if((count&1)==0){
				if(arr[start]>arr[end]){
					rst1+=arr[start];
					start++;
				} else{
					rst1+=arr[end];
					end--;
				}
			} else{
				if(arr[start]>arr[end]){
					rst2+=arr[start];
					start++;
				} else{
					rst2+=arr[end];
					end--;
				}
			}
			count++;
		}
		if(start==end){
			if((count&1)==0)
				rst1+=arr[end];
			else {
				rst2+=arr[end];
			}
		}
		return rst1>rst2?rst1:rst2;
	}
	
	public static void main(String[] args){
		FormALineCoinProblem formALineCoinProblem = new FormALineCoinProblem();
		int[] arr = {8,10,3,6,2,3};
		System.out.println(formALineCoinProblem.getWinValue(arr));
	}
}
